We study reinforcement learning with _multinomial logistic_ (MNL) function approximation where the underlying transition probability kernel of the _Markov decision processes_ (MDPs) is parametrized by an unknown transition core with features of state and action. For the finite horizon episodic setting with inhomogeneous state transitions, we propose provably efficient algorithms with randomized exploration having frequentist regret guarantees. Here, d is the dimension of the transition core, H is the horizon length, T is the total number of steps, and \kappa is a problem-dependent constant. Despite the simplicity and practicality of \texttt{RRL-MNL}, its regret bound scales with \kappa {-1}, which is potentially large in the worst case. To improve the dependence on \kappa {-1}, we propose \texttt{ORRL-MNL}, which estimates the value function using local gradient information of the MNL transition model.